FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs

摘要

Graph analysis performs many random reads and writes, thus, these workloadsare typically performed in memory. Traditionally, analyzing large graphsrequires a cluster of machines so the aggregate memory exceeds the graph size.We demonstrate that a multicore server can process graphs with billions ofvertices and hundreds of billions of edges, utilizing commodity SSDs withminimal performance loss. We do so by implementing a graph-processing engine ontop of a user-space SSD file system designed for high IOPS and extremeparallelism. Our semi-external memory graph engine called FlashGraph storesvertex state in memory and edge lists on SSDs. It hides latency by overlappingcomputation with I/O. To save I/O bandwidth, FlashGraph only accesses edgelists requested by applications from SSDs; to increase I/O throughput andreduce CPU overhead for I/O, it conservatively merges I/O requests. Thesedesigns maximize performance for applications with different I/Ocharacteristics. FlashGraph exposes a general and flexible vertex-centricprogramming interface that can express a wide variety of graph algorithms andtheir optimizations. We demonstrate that FlashGraph in semi-external memoryperforms many algorithms with performance up to 80% of its in-memoryimplementation and significantly outperforms PowerGraph, a popular distributedin-memory graph engine.